#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;


// version 1
//这题考虑的方式是：直接根据题意来找。但是这个思索过程很复杂
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int ret = 0, sum = 0;
        unordered_map<int, int> hash;
        hash[0] = -1;

        for (int i = 0; i < nums.size(); ++i) {
            sum += nums[i];

            int all1 = sum, all0 = i + 1 - sum, target = all1 - all0;
            int index = 0;
             if (hash.count(target)) {
                index = hash[target];
                ret = std::max(ret, i - index);
            }

            //插入哈希
            if (hash.count(target) == 0) hash[target] = i;
        }
        return ret;
    }
};





//version 2
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        for(auto& x : nums) if(!x) x = -1;
        int ret = 0, sum = 0;
        unordered_map<int, int> hash;
        hash[0] = -1;
        for(int i = 0; i < nums.size(); ++i){
            sum += nums[i];

            //只要找到前缀和 == sum的即可
            //多个的话，因为要最长的，所以只需要坐标最靠前的那个即可，只记录最前面那个
            if(hash.count(sum)){
                int index = hash[sum];
                ret = max(ret, i - index);
            }

            if(!hash.count(sum)) hash[sum] = i;
            //如果已经有了，就没必要进行插入了！ 
        }
        return ret;
    }
};